package com.calms.study.leetcode;

import cn.hutool.json.JSONUtil;
import lombok.Getter;
import lombok.Setter;
import lombok.extern.slf4j.Slf4j;

/**
 * 题库:
 * https://www.nowcoder.com/exam/intelligent?questionJobId=10&subTabName=intelligent_page&tagId=273590
 *
 * <p>https://leetcode.cn/problemset/
 *
 * @author wangjunming
 * @since 2024-06-23 11:12
 */
@Slf4j
public class LeetCodeStudy {

  public static void main(String[] args) {

    leetcode004();
  }

  /**
   *
   */
  private static void leetcode004() {

  }

  /**
   * 2. 两数相加 https://leetcode.cn/problems/add-two-numbers/description/
   *
   * <p>给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
   *
   * <p>请你将两个数相加，并以相同形式返回一个表示和的链表。
   *
   * <p>你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
   */
  private static void leetcode003() {

    ListNode listNode01 = new ListNode(2, new ListNode(4, new ListNode(3)));
    ListNode listNode02 = new ListNode(5, new ListNode(6, new ListNode(4)));

    log.info("addTwoNumbers:{}", JSONUtil.toJsonStr(addTwoNumbers(listNode01, listNode02)));
  }

  public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode head = null, tail = null;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {
      int val1 = l1 != null ? l1.val : 0;
      int val2 = l2 != null ? l2.val : 0;

      int sum = val1 + val2 + carry;

      if (head == null) {
        head = tail = new ListNode(sum % 10);
      } else {
        tail.next = new ListNode(sum % 10);
        tail = tail.next;
      }

      carry = sum / 10;

      if (l1 != null) l1 = l1.next;
      if (l2 != null) l2 = l2.next;
    }

    return head;
  }

  @Setter
  @Getter
  public static class ListNode {
    int val;
    ListNode next;

    ListNode() {}

    ListNode(int val) {
      this.val = val;
    }

    ListNode(int val, ListNode next) {
      this.val = val;
      this.next = next;
    }
  }

  /**
   * 1. 两数之和 https://leetcode.cn/problems/two-sum/description/
   *
   * <p>给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
   *
   * <p>你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
   *
   * <p>你可以按任意顺序返回答案。
   */
  private static void leetcode002() {

    int[] nums = {2, 7, 11, 15};
    int target = 9;
    log.info("twoSum:{}", twoSum(nums, target));

    int[] nums2 = {3, 2, 4};
    int target2 = 6;
    log.info("twoSum:{}", twoSum(nums2, target2));

    int[] nums3 = {3, 3};
    int target3 = 6;
    log.info("twoSum:{}", twoSum(nums3, target3));
  }

  public static int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
      for (int j = i + 1; j < nums.length; j++) {
        int i1 = nums[i] + nums[j];
        if (i1 == target) {
          return new int[] {i, j};
        }
      }
    }
    return new int[0];
  }

  /** 在字符串数组中找到最长的公共前缀. */
  private static void leetcode001() {

    String[] strs = {"flow001", "flow002", "flow003", "flow0er", "flow", "flowflight"};
    log.info("longestCommonPrefix:{}", longestCommonPrefix(strs));
  }

  public static String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    String prefix = strs[0];
    for (int i = 1; i < strs.length; i++) {
      // 如果字符串不以prefix开头，则将prefix截取为prefix的前一个字符, 直至等于  prefix
      while (!strs[i].startsWith(prefix)) {
        prefix = prefix.substring(0, prefix.length() - 1);
        if (prefix.isEmpty()) return "";
      }
    }
    return prefix;
  }
}
